A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Upon receiving an incoming packet, the router examines information within the packet to identify the destination for the packet. Based on the destination, the router forwards the packet in accordance with the routing information.
Conventional routers often maintain the routing information in the form of one or more routing tables. The routing tables stores routes through the network, and generally represent the topology of the network. The form and contents of the routing tables often depend on the routing algorithm implemented by the router. Common routing algorithms include distance vector routing algorithms, path vector routing algorithms and link-state routing algorithms. Many of these algorithms make use of the concept of a “hop,” which refers to a connection between two devices. Consequently, the distance between two devices is often measured in hops. Furthermore, in reference to routing a packet, the “next hop” from a network router typically refers to a neighboring device along a given route.
Many high-speed routers include routing engines that generate forwarding information in accordance with the routing information. In particular, the routing engine processes the routing information and other information (such as an access control list or packet processing policy) to select routes to each destination. Based on the selection process, the routing engine generates an action for each destination. This action could be to forward the packet according to forwarding information that associates destinations with specific next hops and ultimately to output ports of the router. Other examples of actions include dropping the packet, counting or logging the packet, or sending the packet to multiple destinations, or combinations of such actions. The term “next hop action” will refer in general to any forwarding decision made on a packet.
Routers commonly implement the forwarding information in the tree-like structure, such as a radix tree having a number of nodes. Upon receiving a packet, a forwarding component of the router uses the forwarding information to select a next hop and output port to which a packet will be forwarded. For example, the forwarding component traverses the nodes of the forwarding tree until reaching a leaf node to make a forwarding decision. Each node within the forwarding tree typically defines a single bit comparison. For example, each node may define a test for a specific bit of a destination “key” read from the packet. Based on the results of each comparison, the router selects another node of the forwarding tree, thereby traversing the tree until a leaf node is reached. The bits tested are referred to as path control bits; the values of the path control bits determine a path through the forwarding tree by a sequence of forwarding tree decisions. The end node of this path determines the next hop action, i.e., the packet forwarding decision.
Depending on the particular deployment of a router, the routing information maintained by the router may define hundreds of thousands of routes and millions of destinations. As result, the forwarding tree may be of considerable size and may contain millions of leaf nodes. Access to the forwarding tree may be costly, as the forwarding tree is typically stored in memory. Each memory access, i.e., access to a different node or set of nodes, introduces delay in forwarding the packet. As a high-speed router seeks to forward millions of packets per second, any delay during the forwarding process can significantly impact the performance of the router.